Corelab Seminar
2014-2015
Aikaterini Nikolidaki
The Price of Local Power Control in Wireless Scheduling
Abstract.
We present a recently published work of Magnus Halldorsson and Tigran Tonoyan, where we seek an assignment of power levels and a partition of the given set of links into the minimum number of subsets satisfying the signal-to-interference-and-noise-ratio (SINR) constraints. Specifically, we are interested in the efficiency of local power assignment schemes, or oblivious power schemes, in approximating wireless scheduling. Presenting the first algorithm, which is known to be best possible for oblivious power schemes. This result is achieved by representing interference by a conflict graph, which allows the application of graph-theoretic results for a variety of related problems, including the weighted capacity problem. We explore further the contours of approximability, and find the choice of power assignment matters; that not all metric spaces are equal; and that the presence of weak links makes the problem harder.